package com.ryujung.linked_list.leetCode_460;

import java.util.HashMap;
import java.util.Map;

class LFUCache {

    class Node {
        int key;
        int val;
        int freq;
        Node next;
        Node pre;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.freq = 1;
        }
    }

    class LinkedNodeList {
        Node head;
        Node tail;

        LinkedNodeList() {
            head = new Node(-2, -2);
            tail = new Node(-1, -1);
            head.next = tail;
            tail.pre = head;
        }

        Node getTail() {
            return tail.pre.val == -2 ? null : tail.pre;
        }

        void addToHead(Node node) {
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }

        void removeTail() {
            Node preTail = tail.pre;
            if (preTail.pre != null && preTail != head) {
                preTail.pre.next = tail;
                tail.pre = preTail.pre;
            }
        }

        void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        boolean isEmpty() {
            return head.next == tail;
        }
    }

    /**
     * 思路：
     * 需要记录每个节点的使用次数，并根据使用次数进行排序
     * 关于排序方式，
     * 想法一是将所有的Node进行线性排序到一个二叉树中，未采用
     * <p>
     * 想法二，是新建一个freqMap，key作为frequence，相同freq的节点形成链表
     * 从链表的头部插入，
     * 每次get和put相同的key，都将节点取出，freq++，并移入下一个fre桶中，
     * 同时放入下一个freq桶的链表首部
     * 还需要单独记录现在cache的minFreq，
     * 如果put导致需要淘汰元素，
     * 就从freqMap中获取mingFreq链表，并将链表的tail节点删除即可
     * <p>
     * 为保证头部插入和尾部删除的时间复杂度为0
     * 链表需要使用双向链表保存前后节点
     */
    private Map<Integer, Node> map = new HashMap<>();
    private Map<Integer, LinkedNodeList> freqMap = new HashMap<>();
    private int capacity;
    private int minFreq = 0;


    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if (capacity == 0) return -1;

        Node node = map.get(key);
        if (node == null) return -1;

        int freq = node.freq;
        LinkedNodeList curFreqList = freqMap.get(freq);
        curFreqList.remove(node);

        // 检查并更新当前reqList
        if (curFreqList.isEmpty()) {
            freqMap.remove(freq);
            // 检查并更新minFreq
            if (minFreq == freq) minFreq++;
        } else {
            freqMap.put(freq, curFreqList);
        }

        node.freq = ++freq;
        LinkedNodeList nextFreList = freqMap.get(freq);
        if (nextFreList == null) {
            nextFreList = new LinkedNodeList();
        }
        nextFreList.addToHead(node);
        freqMap.put(freq, nextFreList);

        return node.val;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;

        Node node = map.get(key);
        if (node == null) {
            LinkedNodeList minList = freqMap.get(minFreq);
            if (minList == null) minList = new LinkedNodeList();

            if (map.size() == capacity) {
                // cache满了，需要删除使用次数最少元素
                Node eliminatedNode = minList.getTail();
                minList.removeTail();
                map.remove(eliminatedNode.key);

                // 如果当前mingFreq桶为空，则从freqMap中删除该桶
                if (minList.isEmpty()) freqMap.remove(minFreq);
            }
            // cache没满，直接插入新元素
            node = new Node(key, value);
            LinkedNodeList curFreqList = freqMap.get(node.freq);
            if (curFreqList == null) {
                curFreqList = new LinkedNodeList();
            }
            curFreqList.addToHead(node);
            minFreq = node.freq;
            map.put(key, node);
            freqMap.put(node.freq, curFreqList);
        } else {
            int freq = node.freq;
            LinkedNodeList curFreqList = freqMap.get(freq);
            curFreqList.remove(node);

            // 检查并更新当前freqList
            if (curFreqList.isEmpty()) {
                freqMap.remove(freq);
                // 检查并更新minFreq
                if (minFreq == freq) minFreq++;
            } else {
                freqMap.put(freq, curFreqList);
            }

            freq++;
            LinkedNodeList nextFreList = freqMap.get(freq);
            if (nextFreList == null) {
                nextFreList = new LinkedNodeList();
            }
            node.freq = freq;
            node.val = value;
            nextFreList.addToHead(node);
            freqMap.put(freq, nextFreList);
            map.put(key, node);
        }
    }

    /**
     * 测试用例:["LFUCache","put","put","get","put","get","get","put","get","get","get"]
     * [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
     * 测试结果:[null,null,null,1,null,2,3,null,1,3,4]
     * 期望结果:[null,null,null,1,null,-1,3,null,-1,3,4]
     */
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

}